struct Primes(Vec<usize>, usize);
impl Primes {
    fn new() -> Primes {
        Primes(vec![2, 3, 5, 7], 10)
    }
    fn expand(&mut self, max: usize) {
        'root: for x in (self.1 + 1)..=max {
            for i in self.0.iter() {
                if x % i == 0 {
                    continue 'root;
                }
                if i.pow(2) > x {
                    break;
                }
            }
            self.0.push(x);
        }
    }
}
struct Square(Vec<usize>, usize);
impl Square {
    fn new() -> Square {
        Square(vec![2, 8, 18], 3)
    }
    fn expand(&mut self, max: usize) {
        let mut x = self.1;
        let mut y = self.0[self.0.len() - 1];
        while y < max {
            x += 1;
            y = x.pow(2) * 2;
            self.0.push(y);
        }
    }
}

/// [Goldbach's other conjecture](https://projecteuler.net/problem=46)
fn main() {
    let mut primes = Primes::new();
    let mut square = Square::new();
    let stat = get_half_sum_stat(10_usize.pow(4), &mut primes, &mut square);
    for (i, s) in stat.iter().enumerate() {
        if *s {
            let x = i * 2 + 1;
            if is_composite(x, &primes) {
                println!("{}", x);
                break;
            }
        }
    }
}

fn get_half_sum_stat(n: usize, primes: &mut Primes, square: &mut Square) -> Vec<bool> {
    let mut stat = vec![true; n];
    let n = n * 2;
    primes.expand(n);
    square.expand(n);
    for x in primes.0.iter() {
        for y in square.0.iter() {
            let z = x + y;
            if z < n && z % 2 == 1 {
                stat[z / 2] = false;
            }
        }
    }
    stat
}

fn is_composite(n: usize, primes: &Primes) -> bool {
    for i in primes.0.iter() {
        if n % i == 0 {
            return true;
        }
        if i.pow(2) > n {
            break;
        }
    }
    false
}
